1. Field of the Invention
The present invention relates to a technique for encrypting and decrypting information to be used, and more particularly to an encryption circuit encrypting and decrypting data with an operation such as power remainder operation, Montgomery operation, addition and subtraction, or the like.
2. Description of the Background Art
As an information technology develops, an emphasis has been placed on ensuring security on a information network (prevention of theft or destruction of data). Accordingly, techniques for encrypting and decrypting information have been adopted in many cases. The technique is applied not only to a field of information and communication technology, but also to more familiar fields such as transportation, finance, medical care, distribution, and the like. With respect to the technique for encryption and decryption of this type, it is demanded that security of high level can be implemented with a simple principle.
Examples related to such techniques are disclosed in Japanese Patent Laying-Open No. 5-324277 and Japanese Patent Laying-Open No. 2002-229445.
A method for encrypted communication disclosed in Japanese Patent Laying-Open No. 5-324277 implements a remainder operation Q=A·BmodN and a power remainder operation C=MemodN by repetition of operations of a similar format Z=U·V·R−1modN using N and R (R: a prime integer).
In addition, a power remainder operation circuit disclosed in Japanese Patent Laying-Open No. 2002-229445 includes an e register holding a key e, a Y register holding a multiplier Y for Montgomery conversion, an N register holding a key N, a B2N register holding a value of 2B+N performed in an operation of Montgomery conversion, an X register holding a plaintext X, an operation circuit performing an operation for encryption and decryption, a P register holding an operation result P, and the like. Thus, the power remainder operation circuit can implement a processing with high speed.
Security of most cryptosystems in present days is based on difficulty in finding a private key through calculation, considering time required therefor. For example, when encryption with RSA (Rivest-Shamir-Adleman scheme) is used, security is based on difficulty in prime factorization of an integer N in a short period of time, which is a product of two prime numbers (N=p×q; p and q are prime numbers). Conversely, this means that, in order to ensure security of the RSA scheme, digits of selected prime numbers p and q must be increased, as performance of a calculator such as a computer is enhanced in the future.
Consider an example in which an encryption circuit having a large bit length is configured according to the inventions disclosed in Japanese Patent Laying-Open No. 5-324277 and Japanese Patent Laying-Open No. 2002-229445 described above. The simplest method is to modify the encryption circuit by increasing registers, however, this is not desirable. This is because the time for operation and the size of the encryption circuit will be increased in accordance with the increase of the registers.
In addition, if the bit length which an addition and subtraction circuit can handle at a time is extended, for example, from 128 bits to 256 bits, a propagation path for a carry in addition and subtraction will be extended, leading to difficulty in raising an operation frequency.